// 最长数对链
class Solution {
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
            int n = pairs.size();
            sort(pairs.begin(),pairs.end());
            for(auto& e : pairs)
            {
                cout << e[0] << " ";
            }
            //dp[i]表示以i为结尾最长数对链个数
            vector<int>dp(n,1);
            for(int i = 1; i < n; i++)
            {
                for(int j = 0; j < i; j++)
                {
                    if(pairs[j].back() < pairs[i].front())
                    {
                        dp[i] = max(dp[j] + 1,dp[i]);
                    }
                }
            }
    
            return *std::max_element(dp.begin(),dp.end());
        }
    };

    // 最长定差子序列。unordered_map用法。
    class Solution {
        public:
            int longestSubsequence(vector<int>& arr, int difference) {
                int n = arr.size();
                int ans = 0;
                unordered_map<int,int>mymap;
                for(auto& e : arr)
                {
                    mymap[e] = mymap[e-difference] + 1;
                    ans = max(mymap[e],ans);
                }
                return ans;
            }
        };